#include <bits/stdc++.h>

#define int ll

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; i++)
#define _rep(i, a, b) for (int i = (a), i##end = (b); i >= i##end; i--)
#define dl make_pair
#define dk(...) make_tuple(__VA_ARGS__)
#define ec first
#define fb second
#define de(x) cerr << #x << " = " << (x) << endl

using namespace std;

typedef long long ll;
typedef __int128 i128;
typedef pair <int, int> pii;

int read() {
	int x = 0, w = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + (ch ^ 48);
		ch = getchar();
	}
	return x * w;
}

template <typename _Tp>
void print(_Tp x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}

int q, a, b;

int to(int a, int b) {
	if (a == b) return 0;
	return a * b / __gcd(a, b);
}

int pfac(int x) {
	rep (i, 2, sqrt(x)) {
		if (x % i == 0) return i;
	}
	return x;
}


signed main() {
#ifndef LOCAL
	freopen("never.in", "r", stdin);
	freopen("never.out", "w", stdout);
#endif
	q = read();
	while (q --> 0) {
		a = read(), b = read();
		const int _gcd = __gcd(a, b);
		//a /= _gcd, b /= _gcd;
		int fac1 = pfac(a), fac2 = pfac(b);
		int ans = to(a, b);
		ans = min(ans, (a == fac1 ? 0 : a) + to(fac1, fac2) + to(fac2, b));
		ans = min(ans, (a == fac1 ? 0 : a) + to(fac1, 2) + to(2, fac2) + to(fac2, b));
		ans = min(ans, (a == fac1 ? 0 : a) + to(fac1, b));
		if (_gcd > 1) ans = min(ans, a + to(_gcd, b));
		print(ans), puts("");
	}
	return 0;
}
